import com.sun.javaws.IconUtil;

import java.util.Arrays;
import java.util.Scanner;

public class Text1 {


    //多数元素：在数组中的个数大于[n/2]
    public static int majorityNum1(int[] arr){
        Arrays.sort(arr);
        return arr[arr.length/2];
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,6,5,5,5,5,5,5,5,5,5,5,5,5,12,53,66};
        int num = majorityNum(arr);
        System.out.println(num);
    }
    //众数，还可以不事先排序，直接找
    public static int majorityNum(int[] arr){
        int count = 0;
        int temp = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == temp){
                count++;
            }else{
                count--;
            }
            if(count == 0){
                temp = arr[i];
                count++;
            }
        }
        return temp;
    }

    //给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况
    // 如果存在，请返回 true ；否则，返回 false
    public static boolean threeOdd(int[] arr){
        int i = 0;
        int count = 0;
        while(count != 3 && i < arr.length){
            if(arr[i] % 2 == 1){
                count++;
                i++;
            }else{
                count = 0;
                i++;
            }
        }
        if(count == 3){
            return true;
        }else{
            return false;
        }
    }
    public static void main18(String[] args) {
        int[] arr = {1,2,3,5,6,7,9,13,10,11,21};
        boolean ret = threeOdd(arr);
        System.out.println(ret);
    }

    public static int singleWomen(int[] arr){
        int ret = arr[0];
        int i = 0 ;
        for (i = 1; i < arr.length; i++) {
            ret ^= arr[i];
        }
        return ret;
    }
    //找到那只单身狗！
    public static void main17(String[] args) {
        int[] arr = {1,27,24,4,4,1,23,6,7,8,24,9,7,2,9,8,6,23,27};
        int ret = singleWomen(arr);
        System.out.println(ret);
    }

    public static int[] sum1(int[] arr, int num){
        int[] ret = new int[2];
        int i = 0;
        int j = 0;

        STOP:
        for (i = 0; i < arr.length-1; i++) {
            for (j = arr.length-1; j > i; j--) {
                if(arr[i] + arr[j] == num){
                    ret[0] = i;
                    ret[1] = j;
                    break ;
                }
            }
        }
        return ret;
    }
    //修改
    public static int[] sum(int[] arr, int num){
        int[] ret = {-1,-1};
        int i = 0;
        int j = 0;

        for (i = 0; i < arr.length-1; i++) {
            for (j = i + 1; j < arr.length; j++) {
                if(arr[i] + arr[j] == num){
                    ret[0] = i;
                    ret[1] = j;
                    return ret ;
                }
            }
        }
        return ret;
    }

    public static void main16(String[] args) {
        int[] arr = {1,5,7,82,13};
        int target = 87;
        int[] ret = sum(arr,target);
        System.out.println(Arrays.toString(ret));
    }

    //冒泡排序，升序
    public static void bubbleSort1(int[] arr){
        int i = 0;
        int j = 0;
        for (i = 0; i < arr.length-1; i++) {
            for (j = 0; j < arr.length-1-i; j++) {
                int temp = 0;
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    public static void bubbleSort(int[] arr){
        int i = 0;
        int j = 0;
        for (i = 0; i < arr.length - 1; i++) {
            boolean flag = false;
            for (j = 0; j < arr.length - 1 - i; j++) {
                if(arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if(flag == false){
                break;
            }
        }
    }
    //冒泡排序的优化：实际上，并不是所有数组都得走完最后一趟才有序，有可能在某一趟就有序了
    public static void main15(String[] args) {
        int[] arr = new int[100000];
        System.out.println(Arrays.toString(arr));
        long start = System.currentTimeMillis();
        bubbleSort1(arr);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
    }




    public static int binarySearch(int[] arr,int num){
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(arr[mid] > num){
                right = mid - 1;
            }else if(arr[mid] < num){
                left = mid + 1;
            }else{
                return mid;
            }
        }
            return -1;
    }
    //有序数组二分查找
    public static void main14(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,14,16,17,19,21,26,56,78};
        System.out.println("请输入要查找的数：");
        int num = sc.nextInt();
        int sub = binarySearch(arr,num);
        if(sub == -1){
            System.out.println("该数字没在数组里！");
        }else{
            System.out.println("找到该数，下标为"+sub);
        }
    }
    //修改：可以直接只用系统给的方法
    //甚至无序的数组，也可以先排序，再二分查找
    public static void main141(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,14,16,17,19,21,26,56,78};
        System.out.println("请输入要查找的数：");
        int num = sc.nextInt();
        int ret = Arrays.binarySearch(arr,num);
        System.out.println(ret);
    }

    public static void main142(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = {3,6,12,46,13,17,33,67,29,64,38,93,57,11,1};
        System.out.println("请输入要查找的数：");
        int num = sc.nextInt();
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int ret = Arrays.binarySearch(arr,num);
        System.out.println(ret);
    }

    public static void oddEven(int[] arr){
        int i = 0;
        int j = arr.length-1;
        while(i < j){
            if(arr[i] % 2 == 1){
                i++;
            }
            if(arr[j] % 2 == 0){
                j--;
            }
            if((arr[i] % 2 == 0)&&(arr[j] % 2 == 1)){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
                j--;
            }
        }
    }
    public static void main13(String[] args) {
        int[] arr = {1,33,45,2,3,4,5,6,7,9,11,23,44,65,68,44,22};
        oddEven(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void transform(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i] * 2;
        }
    }

    public static void main12(String[] args) {
        int[] arr = {2,7,4,11,24};
        transform(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void main11(String[] args) {
        int[] arr1 = {11,11,22,33,44};
        int[] arr2 = {11,11,22,33,44};
        System.out.println(Arrays.equals(arr1,arr2));

        int[] arr3 = new int[10];
        Arrays.fill(arr3,2,7,7);
        System.out.println(Arrays.toString(arr3));
    }
    public static void main10(String[] args) {
        int[] arr = {66,77,88,99};
        int[] ret = new int[arr.length];
        System.arraycopy(arr,1,ret,1,arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(ret));
    }

    public static void main9(String[] args) {
        int[] arr = {1,2,3,4};
        int[] ret = Arrays.copyOfRange(arr,2,4);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(ret));
        ret[0]=111;
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(ret));
    }
    public static void main8(String[] args) {
        int[] arr = {2,8,1,4};
        int[] ret = Arrays.copyOf(arr,2*arr.length);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(ret));
    }
    public static void main7(String[] args) {
        int[] arr = {1,2,3,4,5};
        int[] arr1 = Arrays.copyOf(arr,arr.length);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
        arr1[0] = 999;
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr1));
    }
    public static String myToString(int[] arr){
        String ret = "[";
        for (int i = 0; i < arr.length; i++) {
            ret += arr[i];
            if(i != arr.length-1){
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }
    public static void main6(String[] args) {
        int[] array = {1,7,0,36,9};
        String ret = myToString(array);
        System.out.println(ret);
    }
    public static void doubleOfArray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 2 * arr[i];
        }
    }

    public static int[] doubleOfArray1(int[] arr){
        int[] tempArray = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            tempArray[i] = 2 * arr[i];
        }
        return tempArray;
    }

    public static void main5(String[] args) {
        int[] array = {1,2,3,4,5,6,7};
        int[] ret = doubleOfArray1(array);
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(ret));
    }

    public static void fun1 (int[] array){
        array = new int[]{23,56,79};
        System.out.println(array);
    }
    public static void fun2(int[] array){
        array[0] = 9999;
    }
    public static void main4(String[] args) {
        int[] array1 = {2,4,6,8,2};
        fun2(array1);
        System.out.println(Arrays.toString(array1));
    }
    public static void main3(String[] args) {
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = {4,6,8,9,11};
        arr1 = arr2;
        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
    }

    public static void main2(String[] args) {
        int[] arr1 = {1,2,3,4,5};
        int[] arr2 = arr1;
        arr2[0] = 6666;
        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
     }
    public static void func(){
        int a = 2;
        int b = 1;
        int[] array = new int[3];
    }
    public static void main1(String[] args) {
        int[] array = null;
        System.out.println(array);
        System.out.println(array.length);
    }
}
